package someTestExcemple.huaweiOd.container.stack;
//华为OD机试 - 分奖金 - 栈（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/130959598
//todo 典型单调栈题目 和 阿里巴巴找黄金宝箱(IV)思路一样 加强记忆
import java.util.*;
public class BonusPoints {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] result = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
            result[i] = arr[i]; //每位员工获得的奖金开始默认为他们最初的随机数

        }
        //典型单调栈题目
        //栈中始终保持的是一个递减序列，也就是栈中的每个员工的数字都比后面（栈顶）的员工数字大。
        Stack<Integer> stack = new Stack<>(); //存每位员工往后找到的第一个大于它的位置索引
        for(int i=0;i<n;i++) {
            int num = arr[i];
            //当前元素比栈顶大
            if(!stack.isEmpty() && num >= arr[stack.peek()]) {
                //找到第一个大于栈顶的位置
                int index = stack.pop();
                result[index] = (i-index)*(num-arr[index]);
            } else {
                stack.push(i);
            }
        }
        StringJoiner res = new StringJoiner(" ");
        for(int i=0;i<n;i++) {
            res.add(String.valueOf(result[i]));
        }
        System.out.println(res);
    }
}
